Most computer systems include a processor and a memory system. The speed at which the processor can decode and execute instructions to process data has for some time exceeded the speed at which instructions and operands can be transferred from the main memory of the memory system to the processor. In an attempt to reduce the problems caused by a mismatch in speed, many computer systems also include a cache memory between the processor and the main memory.
A cache memory is a small, high-speed buffer memory which is used to temporarily hold a copy of those portions of the contents of main memory which are likely to be used in the near future by the processor. Typically, when the processor requires an instruction, the instruction is fetched from the cache memory or from the main memory via an instruction bus. The main purpose of a cache memory is to shorten the time necessary to perform memory accesses, either for data or instruction fetch. The information located in cache memory may be accessed in much less time than that located in main memory. Thus, a processor with a cache memory needs to spend far less time waiting for instruction and operands to be fetched and/or stored. For example, in typical large, high-speed computers, main memory can be accessed in 300 to 600 nanoseconds; information can be obtained from a cache memory on the other hand, in 30 to 40 nanoseconds. A cache memory which is used to store instructions as they are used by the processor for possible later re-use, is known as an historical cache memory.
Alternatively, a scheme may be implemented whereby instructions are prefetched and stored in a cache memory before they are requested by the processor. Such a scheme is called a predictive cache memory scheme.
Whether an historical or a predictive cache memory scheme is used, the desired objectives are to 1) maximize the probability of finding a main memory reference's information in the cache, 2) minimize the time required to access information that is needed by the processor (access time), and to 3) minimize the delay due to a cache miss. All of these objectives must be accomplished under cost constraints and in view of the interrelationship between the parameters, for example, the trade-off between hit ratio and access time. The probability of finding the needed information in the cache memory is related to its size.
More recently, cache memories have been coupled with instruction prefetch circuits for providing the storage of future processor instruction requests in the cache, before the processor actually issues the request. When instructions are prefetched from a main memory and written to a cache memory, those prefetched instructions may overwrite previously written instructions stored within the cache. This overwriting of previously written instructions with prefetched instructions is in effect replacing an historical portion of the cache memory with a predictive portion. Although in some instances predictive instruction prefetching provides advantages over historical based caching schemes, there exists a need for a hybrid type of caching scheme whereby some of the information is stored on a predictive basis and some of the information is stored on an historical basis. In most computers, instructions are stored in a main memory in the order that they will be executed. Whereas this order is typically sequential, the instruction flow is often interrupted by conditional and unconditional branch instructions. A register termed the program counter resides in the processor and is incremented at the execution of each instruction and it also stores the address of the next instruction to be executed. When an unconditional branch instruction is executed, the program counter is loaded with the branch target address and the instruction corresponding to the branch target address, the target itself, is executed. After the processor has determined the result of a conditional branch instruction, the program counter will either be loaded with the branch target address or will be loaded with the next sequential address of the instruction following the address of the conditional branch instruction depending on whether or not the condition was satisfied.
Recently, some prefetch circuits have been designed to provide additional functions which enhance the function of prefetching sequential instructions. One such enhancement allows a prefetch circuit to first determine if a current prefetched instruction is a branch instruction. A subsequent prefetched instruction may be the branch target address or may contain the branch target itself. However, when a conditional branch instruction is decoded, the prefetch circuit may not have the necessary information available to determine which path to take because the result of the condition of the conditional branch is not known by the prefetch circuit and thus, a conditional branch may yield an incorrectly prefetched subsequent instruction. By having a part historical, part predictive cache memory, the chance of a cache hit is increased in the instance that a prefetch sequence includes a conditional branch instruction. If the predictive portion of the cache memory does not contain the required instruction due to an incorrectly prefetched instruction, the historical portion of the cache memory may contain the required instruction.
It is thus an object of the invention to improve the performance of a cache memory operation in association with a processor.
It is a further object of the invention to improve the performance of a cache memory by providing a part historic part predictive cache memory system.